In today's communications, digital networks transport large amounts of information. Network services can be, for example, traditional voice phone, facsimile, television, audio and video broadcast, and data transfer.
With the increasing need of information exchange in the global society, the capacity of existing and future networks must be used efficiently. Multiplexers switch different network services to a single network in such a way that every service is fully maintained and does not disturb other services.
Asynchronous Transfer Mode (ATM) is one of the most commonly used communication protocols. ATM is a connection-oriented protocol. ATM protocol assigns virtual channels to each ATM cell. The virtual channel is supported by a physical link. ATM protocol compliant devices process information by framing the information to ATM cells. An ATM cell includes a payload as well as a header. The header includes various fields that map the ATM cell to the virtual channel. These fields include the virtual channel identifier (VCI) field and the virtual path identifier (VPI) field.
The ATM cell is associated with a physical layer (PHY) value that represents the physical link on which the ATM cell arrives or originated from. A device, such as a media access unit, an UTOPIA bus manager as well as an ATM switch associate the PHY value with the ATM cell.
The VCI field is twelve bits long, the VCI field is sixteen bits long and the PHY value is five bits long. It is noted that the PHY value can be longer. Thus, there are at least 233 possible combinations of these fields. When an ATM switch or router receives an ATM cell it has to determine what is the channel associated with that ATM cell. Theoretically there are 233 possible channels, while in practice the number of connections supported by a single ATM switch is much lower.
Various methods were adopted for mapping the very large number of possible channels with a smaller number of channels. One commonly used technique involves hashing. A hashing function maps the 233 space to a much smaller space. The following U.S. patents and patent applications, all being incorporated herein by reference, illustrate some hashing techniques: U.S. Pat. No. 6,034,958 of Wicklund, U.S. patent application publication serial number 2004/0246966A1 of Wu et al., U.S. patent application serial number 2004/0131062A1 of Horie, U.S. Pat. No. 6,760,345 of Rosengard, U.S. Pat. No. 6,735,191 of Hosein, U.S. patent application serial number 2004/0001451 of Bernheim et al., U.S. patent application serial number 2003/0043806A1 of Davis et al., U.S. patent application serial number 2003/0081610A1 of Bharucha et al., and U.S. Pat. No. 6,535,526 of Oyamada et al.
Typical hashing functions require a relatively large number of memory accesses and data processing stages.
There is a need to provide efficient methods and devices for processing ATM cells.